Large distributed data networks, such as the Internet, allow data to be shared between computers connected to the network. One protocol for such file sharing is the Hypertext Transfer Protocol (“HTTP”) which is used to implement the World Wide Web (“the web”). Computers allow users to specify files to be retrieved over the web. Files can include image, sound, or other data files. Web pages written in HTML (Hypertext Markup Language) can be requested, and can include embedded references to files to be retrieved and embedded on the web page as displayed.
Because retrieving data over the network may be time-consuming and expensive, and data may be required more than once, caching web proxies have been developed. These are computer systems dedicated to caching and delivering web content. Typically, they exist on a firewall or at the point where an Internet Service Provider (“ISP”) peers with its network access provider. These caching web proxies store copies of information downloaded from other computers on the network, and provide the information to users rather than downloading the same information over and over from the remote computer.
Caching web proxies reduce request load on remote servers, improve web client latency (the speed at which the web client can provide requested information), reduce variability in access time, improve the perceived availability of remote servers, and drive down network access costs. Caching web proxies store cached information in main memory and on disks. Recently used information is usually kept in main memory, while the rest is stored on disks. Prior art web proxies use a traditional file system to store information on disk, which causes multiple inefficiencies.
One problem with caching web proxies is that traditional file systems often include their own cache of data recently accessed. Thus, if the file system and the web proxy both cache data, multiple buffering may occur, which will drive down the hit rate by reducing the amount of memory used to store useful files. Another problem is that, when a file is requested from a file system, the file will be copied from the file system's buffer to the applications' address space. This copying takes time.
Two standard web proxies in common use are Squid (free software, copyrighted by the University of California San Diego, see http://www.squid-cache.org) and Apache (copyrighted by The Apache Software Foundation, see http://www.apache.org). These systems use the standard file system services provided by the host operating system. On a UNIX system, this will often be some variation or descendant of the 4.2 BSD UNIX Fast File System (“FFS”).
On most UNIX file systems, including FFS, files are represented by collections of fixed-size blocks, typically 8 KB in size. When accessing a file, disk delays occur due to disk seeks occurring when the file blocks are not stored contiguously on disk. These file systems attempt to minimize the disk head positioning time by storing the file blocks contiguously and prefetching blocks when a file is being accessed sequentially. This strategy is successful for files that are less than 128 KB (on standard FFS configuration parameters). Thus when the workload is comprised mainly of small files, the largest source of disk delay is when the small files being requested are not stored near each other on the disk. FFS attempts to reduce this delay by having the user place files into directories, and locating files in a directory on a group of contiguous disk cylinders called cylinder groups. The responsibility for performance, then, relies on an application or user who must construct a directory hierarchy organized in a way which matches future usage patterns. In order to keep file lookup times low, the directory hierarchy must also be well-balanced and a single directory must not have too many entries. Squid and Apache both attempt to reduce data retrieval times by using a directory system. Squid attempts to balance the directory hierarchy, but in the process distributes documents referenced consecutively across directories. If documents are then re-referenced in the same order, different directories must be accessed, which will increase latency.
In FFS, data about the location of files (“file meta-data”) is stored in the i-node structure, which is updated using synchronous disk writes to ensure data integrity. These synchronous writes may even be performed when a file is only being read to update some pieces of the meta-data. Since a web cache does not rely on file durability for correctness, such synchronous writes are not necessary—asynchronous writes could be used, which would improve performance. In addition, some of the file meta-data may not be needed by the application. Therefore FFS is limited in a way which adversely affects performance.
FFS was designed for workstation workloads, and is not optimized for the workload and requirements of a web proxy. Because file system latency is a key component in web client latency (see Alex Rousskov, Duane Wessels, and Glen Chisholm, “The First IRCache Web Cache Bake-Off—The Official Report” April 1999, available at http://www.bakeoff.ircache.net/bakeoff-01/) improving file system latency is of key importance to improving web proxy performance.
Some commercial vendors, such as CacheFlow (distributed by CacheFlow Inc., see www.cacheflow.com) have improved performance by rebuilding the entire system stack—by implementing a special operating system with an application-specific file system executing on special hardware. These solutions are expensive.
Web proxies have certain workload characteristics which are unexploited by current caching systems. Files are always accessed sequentially and in their entirety. In one sample, it was found that most cacheable web documents are small with a median file size approximately 2 KB and average request size was 6167 B. Over 90% of the references in the sample were for documents smaller than 8 KB. Client web accesses generally consist of a request for an HTML page, followed by requests for the embedded data referenced in that page. We have termed these files together a locality set. When the HTML page is rereferenced, many of the same files from the initial locality set are again requested. Locality sets themselves are not much larger than files. In one sample, 42% were found to be 32 KB or smaller, 62% 64 KB or smaller, 73% 96 KB or smaller, and 80% 128 KB or smaller.
Web proxies also experience a large variability in workload and have frequent idle periods. This idle period can be exploited but has not been in prior art products.
This invention also relates to a method for implementing an improved file system cache for use with a file system which needs a high performance cache. In particular, this invention relates to a method for implementing a file system cache running on top of a raw disk partition to improve throughput by reducing the number of disk operations that must be performed in order to retrieve cached information.